package 二叉树层序遍历.二叉树层序遍历II;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Solution {
    /*
    给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
     */
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        // 利用 二叉树层序遍历I 中的思路，只需要修改 List 的添加方式即可
        // 核心思路：
        // ① 通过队列进行辅助遍历,遍历当前节点(处理当前层),并把当前节点的左右孩子放入队列中(他们属于下一层,待处理)
        // ② 利用 last指针 记录每一层的最后一个节点,当 last 指针和当前遍历的节点相同时，就更新 last 指针为队列的最后一个节点

        if (root == null)
            return Collections.emptyList();

        List<List<Integer>> result = new ArrayList<>();
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        TreeNode p, last = root;
        queue.offer(root);
        ArrayList<Integer> list = new ArrayList<>();
        while (!queue.isEmpty()) {
            // 遍历当前节点(处理当前层)
            p = queue.poll();
            list.add(p.val);
            // 并把当前节点的左右孩子放入队列中
            if (p.left != null) queue.offer(p.left);
            if (p.right != null) queue.offer(p.right);
            // 如果相等则代表当前层处理结束(处理下一层)
            if (last == p) {
                last = queue.peekLast();
                result.add(0, list);
                list = new ArrayList<>();
            }
        }
        return result;
    }
}